Art und Inhalt |
| Title: |
Algorithm, Logic, Complexity |
| Lecturer: |
Prof. Dr. Rüdiger Reischuk |
| Classification: |
Master Informatik und Master Entrepreneurship in digitalen Technologien
Master IT-Sicherheit (Vertiefungsmodul)
Vertiefungsmodul 12 KP, Technologiefach Informatik, Beliebiges Fachsemester
Lehrformen: Vorlesung, seminaristischer Unterricht, Bearbeitung eines individuellen Themas inkl. Vortrag und schriftliche Ausarbeitung
Prüfung: mündlich, Termine nach individueller Vereinbarung |
| Content: |
- Maschinenmodelle
- Problemreduktion und Maschinensimulation
- Komplexitätsklassen und Hierarchien
- Descriptive Komplexität
- Logische Kalküle und Beweissysteme
- Schaltkreis- und Kommunikations-Komplexität
- Algorithmisches Lernen
- Algorithmische Spieltheorie
- Nichtstandardberechnungsmodelle, Quantum Computing
|
| Competence: |
- Fähigkeit, komplexe algorithmische Problemstellungen adäquat formal beschreiben zu können
- Tieferes Verständnis der Methoden algorithmischer Modellierung und Analyse
mit Hilfe von Maschinenmodellen
- Komplexitätsanalysen komplexer Problemstellungen durchführen können und die dazu eingesetzen
Techniken beherrschen
- Fähigkeit, algorithmische Probleme bezüglich ihrer Komplexität einzuordnen und
daraus Lösungsmethoden abzuleiten
- Bedeutung unterer Komplexitätsschranken verstehen und die Beweistechniken nachvollziehen können
|
| Literature: |
- R. Reischuk: Einführung in die Komplexitätstheorie - Teubner, 1990
- S. Arora, B. Barak: Computational Complexity - Cambridge UP 2009
- C. Papadimitriou: Computational Complexity - Addison-Wesley, 1994
- M. Kearns, V. Vazirani: An Introduction to Computational Learning Theory - MIT Press, 1997
- R. Downey, M. Fellows: Fundamentals of Parameterized Complexity, Springer 2013
- N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory, Cambridge UP, 2007
- D. Kozen: Theory of Computation - Springer, 2006
|
|
|
Lecture |
| Lecturer |
Prof. Dr. Rüdiger Reischuk |
| Credits |
2 SWS |
| Hours |
|
Exercises |
| Assistent |
Marcel Wienöbst M.Sc. |
| Credits |
2 SWS |
| Hours |
|
